// answer[i] = i左侧前缀积 * i右侧后缀积
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> answer(nums.size());
        answer[0] = nums[0];
        // 计算出前缀积
        for (int i = 1; i < nums.size(); ++i) {
            answer[i] = nums[i] * answer[i - 1];
        }

        // 延迟计算后缀积，并乘到结果里
        int suffixMultiple = 1;
        for (int i = nums.size() - 1; i > 0; --i) {
            answer[i] = answer[i - 1] * suffixMultiple;
            suffixMultiple *= nums[i];
        }
        answer[0] = suffixMultiple;
        return answer;
    }
};